#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=139 lang=cpp
 *
 * [139] 单词拆分
 */

// @lc code=start
class Solution {
public:
    // 搜索方法
    // bool wordBreak(string s, vector<string>& wordDict) {
    //     return helper("", s, wordDict, 0);
    // }

    // bool helper(string now, const string& origin, vector<string> & wordDict, int index) {
    //     if (now.size() > origin.size()) return false;
    //     if (now == origin) return true;
    //     for (int i = 0; i < wordDict.size(); i++) {
    //         if (origin.substr(index, wordDict[i].size()) == wordDict[i]) {
    //             string x = now;
    //             x.append(wordDict[i]);
    //             if (helper(x, origin, wordDict, index + wordDict[i].size())) return true; 
    //         }
    //     }
    //     return false;
    // }

    // 动态规划
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> record;
        for (int i = 0; i < wordDict.size(); i++) record.insert(wordDict[i]);
        vector<bool> dp(s.size() + 1, false); // s的前i个单词是否匹配
        dp[0] = true;
        for (int i = 1; i < s.size() + 1; i++) {
            for (int j = 0; j < wordDict.size(); j++) {
                if (i >= wordDict[j].size()) {
                    int sz = wordDict[j].size();
                    dp[i] = dp[i] | (dp[i - sz] && (s.substr(i - sz, sz) == wordDict[j]));
                }
            }
        }
        return dp[s.size()];
    }
};
// @lc code=end

